\chapter{机器学习听课笔记}
\section{第一集}
\section{第二集}
\textbf{	记号：}
	\begin{table}[H]
		\begin{tabular}{ll}
	m: & 样本数		\\
x: & 输入、特征\\
y: & 响应\\
(x,y): & 训练数据\\
$ (x^{(i)},y^{(i)}) $：&第$ i $个训练样本\\
$ h $：&函数,$ h(x)=\theta_0+\theta_1x_1+\theta_2x_2=\theta^T x $\\
n:& x的个数\\
		\end{tabular}
	\end{table}

机器学习就是要最小化
\[ J(\theta)=\frac{1}{2}\sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})^2 \]

\textbf{梯度下降算法：}
\[ \theta_i:=\theta_i-\alpha\frac{\partial }{\partial \theta_i} J(\theta)=\theta_i-\alpha\sum_{m}^{i=1}(h_{\theta}(x^{(j)})-y^{(j)})\cdot x_i^{(j)}\]

$ \alpha $是学习参数，控制了下降的速度，通常是手动设置，过小则慢，过大则可能跨过最大值。

\textbf{随机梯度下降算法：}

如果你有大量训练样本，你也许你会使用随机梯度下降，这样就不用像梯度下降算法那样对所有样本求和，你只需要一个样本一个样本的往下算。优点是算的快了，缺点是可能不会精确收敛。算法如下，

For j=1 to m \{
\[ \theta_i:=\theta_i \alpha(h_\theta(x^{(j)})-y^{(j)})x_i^{j},\hspace{2em}\text{for all }i\]

\}

\textbf{矩阵表达推导出了OLS算法：}

\[ \nabla_\theta J=\begin{bmatrix}
\frac{\partial J}{\partial\theta_0}\\
\vdots\\
\frac{\partial J}{\partial\theta_n}
\end{bmatrix}\in R^{n+1} \]

\[\bm{\theta}:=\bm{\theta}-\alpha\nabla_\theta\bm{J}\]

\[ f:R^{m\times n}\rightarrow R\hspace{2em} f(A),A\in R^{m\times n} \]

\[ \nabla_Af(A)=\begin{bmatrix}
\frac{\partial f}{\partial A_{11}}&\cdots& \frac{\partial f}{\partial A_{1n}}\\
\vdots & \ddots & \vdots\\
\frac{\partial f}{\partial A_{n1}}&\cdots& \frac{\partial f}{\partial A_{nn}}\\
\end{bmatrix} \]

如果$ A $是一个方阵，那么，
\[ \text{tr}A=\sum_{i=1}^n A_{ii} \]

典型事实：
\[ \text{tr}AB=tr BA \text{tr}(ABC)=\text{tr}(CAB) \]
\[ f(A)=\text{tr}AB\hspace{1em} \nabla _Atr(AB)=B^T \hspace{1em}\text{tr}(A)=\text{tr}A^T\]

\section{第三集}

\textbf{局部加权线性回归算法}

\textbf{分类问题}

$ y\in \{0,1\},h_\theta\in[0,1] $，可以选择，
\[ h_\theta(x)=g(\theta^Tx)=\frac{1}{1+e^{-\theta^Tx}} \]

\begin{align*}
 &P(y=1|x;\theta)=h_\theta(x)\\
 &P(y=0|x;\theta)=1-h_\theta(x)\\
& P(y|x;\theta)=h_\theta(x)^y(1-h_\theta(x))^{1-y}\\
\end{align*}

似然函数为:
\[ L(\theta)=P(y|x;\theta)=\Pi_{i=1}^mh_\theta(x^{(i)})^{y^{(i)}}(1-h_\theta(x^{(i)}))^{1-y^{(i)}}\]

对数似然为，
\[ l(\theta)=\sum_{i=1}^{m}y^{(i)}\ln h_\theta(x^{(i)})+(1-y^{(i)})\ln (1-h_\theta(x^{(i)})) \]

\[ \theta:=\theta+\alpha\nabla_\theta l(\theta) \]


\section{第四集}
\textbf{牛顿算法}

该算法通常比梯度算法要快很多。若要找一个$ \theta $使得$ f(\theta)=0 $，怎么办？可以先随便找一个$ \theta^{(0)} $，并画出该点上该函数的切线，该切线与x轴有一个交点，记为$ \theta^{(1)} $，再计算该点的切线与x轴的交点，记为$ \theta^{(2)} $，以此类推，直到找到$ f(\theta)=0 $的点。


\[ \theta^{(0)}=\theta^{(0)}-\frac{f(\theta^{(0)})}{f'(\theta^{(0)})} \]

$ f'(\theta) $就是那个正切函数。

因此对于似然函数而言，无非就是求$ l'(\theta)=0 $，因此，
\[ \theta^{(t+1)}=\theta^{(t)}-\frac{l'(\theta^{(t)})}{l''(\theta^{(t)})} \]

牛顿算法是二次收敛。通俗地讲，若你一次迭代后，误差为0.1，再一次迭代误差会为0.01。

一般地，
\[ \bm{\theta}^{(t+1)}=\bm{\theta}^{(y)} -H^{-1}\nabla_\theta \bm{l}\]

其中，$ \bm{H} $是海塞矩阵。

\textbf{指数分布族}
\[ P(y;\eta)=b(y)\exp[\eta^TT(y)-a(\eta)] \]

其中$ \eta $称为自然参数,$ T $是充分统计量。伯努利分布和高斯分布都是指数分布族的特例，只要选不同的$ a,b\text{和}T $即可。

伯努利分布：
\begin{align*}
Ber(\phi):&P(y=1;\phi)=\phi\\
P(y;\phi)&=\phi^y(1-\phi)^{(1-y)}\\
& = \exp(\ln \phi^y(1-\phi)^{(1-y)})\\
& = \exp[y\ln \phi+(1-y)\ln(1-\phi)]\\
& = \exp\left[\ln \frac{\phi}{1-\phi}y+\ln (1-\phi)\right]
\end{align*}

正态分布：
\begin{align*}
\mathcal{N}(\mu,\sigma^2)
\end{align*}

多项式分布（多类别）：

$ y\in\{1,\cdots,k\} $，参数为$ \phi_1,\cdots,\phi_k $，$ \phi_k=1-\phi_1-\cdots,\phi_{k-1} $。

示性函数$ \bm{1}\{\text{True}\}=1 $。

\[ T(1)=\begin{bmatrix}
1\\0\\\vdots\\0
\end{bmatrix} ,T(2)=\begin{bmatrix}
0\\1\\\vdots\\0
\end{bmatrix},T(k-1)=\begin{bmatrix}
0\\0\\\vdots\\1
\end{bmatrix},T(k)=\begin{bmatrix}
0\\0\\\vdots\\0
\end{bmatrix}\]

\[ P(y)= \]

最终可以得到，
\[ \phi_i=\frac{e^{\eta_i}}{1+\sum_{i=1}^k e^{\eta_i}} \]

像这种$ k $类问题，也称为softmax回归。


\section{第五集}
\subsection{高斯判别分析和logistic}
可以为良性肿瘤建模，再给恶性肿瘤建模，当有一个新病人，分别计算两个模型中的概率，较大的就是何种肿瘤。这种算法称为生成算法。

对参数$ \phi,\mu_0,\mu_1,\Sigma $的似然，


一般地，$ x|y\sim \mathcal{N} \Longrightarrow \text{logistic for } p(y=1|x)$，但反过来不成立。实际上，若$ x|y=1\sim \text{Poisson}(\lambda_1),x|y=0\sim \text{Poisson}(\lambda_0) \Longrightarrow p(y=1|x) \text{is logistic}$。所以\textbf{高斯判别分析有一个更强的假定}。不过，如果高斯分布不满足，通常也有着很好的算法，该算法参数较少，需要的样本也较少。

\subsection{\textbf{垃圾邮件分类——朴素贝叶斯}}

该模型对文本分类非常效果棒，即使接下来该算法的假设，很可能不成立，但算法的确有效。

我有一个字典包含诸如\{a,audwork,$\cdots$,buy,$\cdots$,\}（譬如过去两个月中我的邮件中出现两到三次的单词），譬如50000个单词（一般几百个到几千个），这个是特征变量。然后可以构造一个向量，
\[x=\begin{bmatrix}
1\\0\\0\\\vdots\\0\\\vdots\\0
\end{bmatrix}\begin{matrix}
a\\audwork\\buy\\\vdots\\cs229\\\vdots\\way
\end{matrix}\]

$ x $的含义表明若字典里有该单词，则取值为1，该向量的维度为$ n $。若直接给$ p(x|y) $建模，因为$ x $的维度为50000，因此$ x $可能的值为$ 2^{50000} $，这个参数就太多了。我们需要另外一种建模算法，该算法有一个假设，即给定$ y $（$ y $是哑变量，标识是否垃圾邮件），诸$ x $独立。于是有，

\begin{align*}
 p(x_1,x_2,\cdots,x_n|y)&=p(x_1|y)p(x_2|y,x_1)\cdots\\
&= P(x_1|y)P(x_2|y)\cdots P(x_{n}|y)\\
& = \Pi_{i=1}^{n}p(x_i|y)
\end{align*}

上式中的$ p(x_i|y) $就是参数：
\begin{align*}
\phi_{i|y=1}=p(x_i=1|y=1)\\
\phi_{i|y=0}=p(x_i=1|y=0)\\
\phi_y=p(y=1)
\end{align*}

结合上面两个式子，就可以写出联合似然函数，
\[ \ell(\phi_y,\phi_{i|y=1},\phi_{i|y=0})=\Pi_{i=1}^m p(x^{(i)},y^{(i)}) \]

然后最大化，可以得到参数的估计，
\begin{align*}
\phi_{j|y=1}=\frac{\sum_{i=1}^m \bm{1}\{x_j^{(i)}=1,y^{(i)}=1\}}{\sum_{i=1}^m\bm{1}\{y^{(i)}=1\}}\\
\phi_y=\frac{\sum_{i=1}^m\bm{1}\{y^{(i)}=1\}}{m}
\end{align*}

这样，我们就拥有了$ p(x|y),p(y) $，于是就可以得到$ p(y|x) $。

\subsection{一个修正算法——Laplace平滑}
一般情况下，
\[ p(y=1)=\frac{\# 1s}{\# 1s+\# 0s} \]

但是Laplace平滑算法认为，
\[ p(y=1)=\frac{\#1s+1 }{\# 1s+1+\# 0s+1} \]

\section{第六集:朴素贝叶斯、神经网络、SVM}
\subsection{朴素贝叶斯}
之前那个分类模型可以称之为多元伯努利模型。现在这个可以称为多项式分类模型。

\subsection{神经网络}
讲得很简单，以后看他的深度学习资料。

作者支出神经网络是需要定制的，譬如层数怎么选等。但SVM不需要定制。
\subsection{SVM}
\textbf{标识：}

\[ y\in\{1,-1\}, \hspace{2em}g(z)=\begin{cases}
1\hspace{2em} &\text{if }z\ge 0\\
-1\hspace{2em} &\text{if otherwise}\\
\end{cases}\]

过去，一般用$ h_\theta(x)=g(\theta^Tx) $，现在换一种写法，写作，
\[ h_{w,b}(x)=g(w^Tx+b) \]

其中$ b $是截距。

\textbf{函数间隔$\hat \Gamma $}:定义点$ x^{(i)},y^{(i)} $到超平面$(w,b)  $的函数距离为，
\[\hat \Gamma^{(i)}=y^{(i)}(w^Tx^{(i)}+b) \]

其含义在于，
\begin{itemize}
	\item 如果$ y^{(i)}=1 $，则希望$ w^Tx^{(i)}+b\gg 0 $；
	\item 如果$ y^{(i)}=-1 $，则希望$ w^Tx^{(i)}+b\ll 0 $。	
\end{itemize}

但是，如果我们同时扩大$ w,b $，则函数距离会无限扩大，因此单纯扩大函数间隔没有意义，必须要有一个约束，一般使用$ \parallel w\parallel=1 $。

\textbf{几何间隔$ \Gamma $}

分隔平面的单位法向量为$ \frac{w}{\parallel w\parallel} $（证明见课本），若点$ (x^{(i)},y^{(i)}) $到分隔平面的距离记为$ \hat \Gamma^{(i)} $，那么根据向量几何，点$ (x^{(i)},y^{(i)}) $在该分隔平面的投影点可以写为$ x^{(i)}-\Gamma^{(i)}\frac{w}{\parallel w\parallel} $，因为该点在该平面上，所以它也应该满足，
\[ w^T\left(x^{(i)}-\Gamma^{(i)}\frac{w}{\parallel w\parallel}\right)+b=0 \]

将上式展开，可得，
\begin{align*}
& w^Tx^{(i)}+b=\Gamma^{(i)}\frac{w^Tw}{\parallel w\parallel}=\Gamma^{(i)}\parallel w\parallel \\
\Longrightarrow \hspace{2em}& \Gamma^{(i)}=\left(\frac{w}{\parallel w\parallel}\right)^Tx^{(i)}+\frac{b}{\parallel w\parallel}
\end{align*}

实际上，上面那个叫符号距离。更一般地，需要符号来限定，
\[ \Gamma^{(i)}=y^{(i)}\left(\frac{w^T}{\parallel w\parallel}x^{(i)}+\frac{b}{\parallel w\parallel}\right) \]

可见函数间隔和几何间隔就差一个$ \parallel w\parallel $因子。

以上是单个点的几何间隔，那对于全体样本而言，我们需要在这么多样本中找一个最小的几何间隔，
\[ \Gamma = \min_i \Gamma^{(i)} \]

然后我们需要通过选择$\Gamma, w,b $使得这个有着最小几何间隔的样本，它的几何间隔最大，
\begin{align*}
 \max_{w,b,\Gamma}\; & \Gamma\\
 s.t. & \; y^{(i)}(w^Tx^{(i)}+b)\ge \Gamma\\
 & \parallel w\parallel =1
\end{align*}

\section{第七集：SVM}
\subsection{优化问题的改写}
对于上一集的最优化问题，
\begin{align*}
\max_{w,b,\Gamma}\; & \Gamma\\
s.t. & \; y^{(i)}(w^Tx^{(i)}+b)\ge \Gamma\\
& \parallel w\parallel =1
\end{align*}

其中约束条件$ \parallel w\parallel=1 $是一个非凸约束（它是一个球体），我们要极力避免非凸约束。因此，可以把上述优化问题修改为，
\begin{align*}
\max_{w,b,\Gamma}\; & \frac{\Gamma}{\parallel w\parallel}\\
s.t. & \; y^{(i)}(w^Tx^{(i)}+b)\ge \Gamma
\end{align*}

同时，$ w,b,\Gamma $又不是互相独立的，要知道$ \Gamma=\min y^{(i)}(w^Tx^{(i)}+b) $，通过修改$ w,b $就可以修改$ \Gamma $，因此，完全可以约束$ \Gamma=1 $，只通过调节$ w,b $来解最优化问题，所以，上述优化又可以写成，
\[\begin{matrix}
\max_{w,b}\; & \frac{1}{\parallel w\parallel}\\
s.t. & \; y^{(i)}(w^Tx^{(i)}+b)\ge 1	
\end{matrix}\Longrightarrow
\begin{matrix}
\min_{w,b}\; & \parallel w\parallel^2\\
s.t. & \; y^{(i)}(w^Tx^{(i)}+b)\ge 1
\end{matrix}\]

\subsection{拉格朗日对偶问题}
考虑如下最优规划，
\begin{align*}
\min \;&f(w)\\
s.t.\; &g_i(w)\le 0, i =1,\cdots,k\\
&h_i(w)=0\; i=1,\cdots,l
\end{align*}

其拉格朗日函数为，
\[\mathcal{L}(w,\alpha,\beta)=f(w)+\sum_{i=1}^k\alpha_ig_i(w)+\sum_{i=1}^l\beta_ih_i(w)\]

然后可以定义如下问题，脚标$ p $表示是原始（primal）问题，
\begin{align*}
\Theta_p(w)=\max_{\alpha,\beta,\alpha_i\ge 0}\;&\mathcal{L}(w,\alpha,\beta)
\end{align*}

考虑如下等式，
\[ p^*=\min_w\max_{\alpha,\beta,\alpha_i\ge 0}\mathcal{L}(w,\alpha,\beta)=\min_w\Theta_p(w) \]

现在看看$ \Theta_p(w) $到底是什么，
\begin{itemize}
	\item 如果违反了其中一个约束，如$ g_i(w)>0 $，那么只要增大$ \alpha $，就可以无限增大$ \mathcal{L} $;
	\item 类似地，若$ h_i(w)\ne 0 $，也可以通过选择$ \beta $，使得$ \mathcal{L} $无限增大。
\end{itemize}

可见，只要满足关于$ g_i(w),h_i(w) $的约束条件，那么，
\[ \Theta_p(w)=f(w) \]

于是，我们将$ p^*=\min_w\; \Theta_p(w) $称为\textbf{原始问题}。

现在来看\textbf{对偶问题},若定义，
\[ \Theta_D(\alpha,\beta)=\min_w\;\mathcal{L}(w,\alpha,\beta) \]

则，
\[ d^*=\max_{\alpha\ge 0,\beta}\min_w\mathcal{L}(w,\alpha,\beta)=\max_{\alpha\ge 0,\beta}\Theta_D(\alpha,\beta) \]


注意到原始问题与对偶问题的区别仅仅在于最大化和最小化的顺序不同。一般情况下有典型事实，

\[ \max\min(\cdot)\le \min\max(\cdot)\hspace{2em} \text{即，} d^*\le p^*\]

譬如你可以考察一下这个特例，$ \max_{y\in\{0,1\}}\min_{x\in\{0,1\}}\bm{1}\{x=y\}\le \min_{x\in\{0,1\}}\max_{y\in\{0,1\}}\bm{1}\{x=y\} $。但在某些条件下，这个优化会取相同的值。

这个具体条件如下，
\begin{itemize}
	\item $f$是凸的，可以通俗理解为$ H\ge 0 $；
	\item $ h_i $是一个仿射函数，也即$ h_i(w)=a^Tw+b $（要有截距项）；
	\item $ g $是严格可行的，也即$ \exists w,s.t. \forall i,g_i(w)<0 $
\end{itemize}

然后，$ \exists w^*,\alpha^*,\beta^*,s.t. w^* $是原始问题的解，$ \alpha^*,\beta^* $是对偶问题的解，
\begin{itemize}
	\item  $ p^*=d^*=\mathcal{L}(w^*,\alpha^*,\beta^*) $;
	\item \[ \frac{\partial \mathcal{L}(w^*,\alpha^*,\beta^*)}{\partial w}=0,\hspace{1em} \frac{\partial \mathcal{L}(w^*,\alpha^*,\beta^*)}{\partial \beta}=0,\hspace{1em}\]
	\[ \alpha^*_ig_i(w^*)=0,\alpha^*_i\ge 0, g_i(w^*)\le 0 \hspace{2em}\text{（KKT条件）}\]
\end{itemize}

\subsection{SVM的算法}
换一种标识，
\begin{align*}
 \alpha,\beta\rightarrow &\;\alpha \\
 w\rightarrow &\;w,b
\end{align*}

回到前面的优化问题，
\begin{align*}
\min_{w,b}\; & \frac{1}{2}\parallel w\parallel^2\\
s.t. & \; y^{(i)}(w^Tx^{(i)}+b)\ge 1
\end{align*}

根据拉格朗日对偶的符号表述，可以重写为，
\begin{align*}
\min_{w,b}\; & \frac{1}{2}\parallel w\parallel^2\\
s.t. & \; g(w,b)=1-y^{(i)}(w^Tx^{(i)}+b)\le 0
\end{align*}

然后KKT条件意味着，
\begin{align*}
 \alpha_i>0 \Longleftrightarrow g_i(w,b)=0 \text{函数间隔等于1}\\
 \alpha_i=0 \Longleftrightarrow g_i(w,b)<0 \text{函数间隔大于1}
\end{align*}

那么它的含义是什么呢？往往会存在几个少数的样本，其函数间隔是等于1的，其他都是大于1的。这几个少数的样本，我们就称之为\textbf{支持向量}。

最优化问题的拉格朗日表述为，
\begin{equation}\label{6-1}
 \mathcal{L}(w,b,\alpha)=\frac{1}{2}\parallel w\parallel^2-\sum_{i=1}^m\alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1]
\end{equation}

其对偶问题最里面那个规划为，
\[ \Theta_D(\alpha)=\min_{w,b}\mathcal{L}(w,b,\alpha) \]

该规划的一阶条件为，
\begin{align}\label{6-2}
\nabla_w\mathcal{L}(w,b,\alpha)&=w-\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}=0\Longrightarrow w=\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}\\\label{6-3}
\nabla_b\mathcal{L}(w,b,\alpha)&=-\sum_{i=1}^my^{(i)}\alpha_i=0
\end{align}

现在把\eqref{6-2}式代入到\eqref{6-1}式中，就可以得到$ \Theta_D(\alpha) $，具体有，
\begin{align*}
\mathcal{L}&=\frac{1}{2}w^Tw-\sum_{i=1}^m\alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1]\\
& =\left(\sum_{i=1}^m\alpha_ix^{(i)}y^{(i)}\right)^T\left(\sum_{j=1}^m\alpha_ix^{(j)}y^{(j)}\right)-\sum_{i=1}^m\alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1]\\
& = \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_j\langle x^{(i)},x^{(j)}\rangle-\sum_{i=1}^m\sum_{j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_j\langle x^{(i)},x^{(j)}\rangle+\sum_{i=1}^m\alpha_i\\
&=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_j\langle x^{(i)},x^{(j)}\rangle\\
& := W(\alpha)
\end{align*}

此时对偶问题为，
\begin{align}\nonumber
\max\; &W(\alpha)\\\label{7-1}
s.t.\;& \alpha_i\ge 0\\\nonumber
& \sum_{i=1}^m y^{(i)}\alpha_i=0\hspace{2em}\text{照搬了\eqref{6-3}式}
\end{align}

然后，针对上述规划，若解出了$ \alpha $，则利用\eqref{6-2}式就可以得到$ w $，有了$ w $意味着超平面的法线已经确定，只需要考虑如何移动超平面在哪个位置即可。一般地，可以最终得到，
\[ b=\frac{\max_{i:y^{(i)}=-1}w^Tx^{(i)}+\min_{i:y^{(i)}=1}w^Tx^{(i)}}{2} \]

然后，此时，若你有一个新的观测，你要预测它时，可以计算，
\begin{align*}
 h_{w,b})(x)&=g(w^Tx+b) \\
 & = \sum_{i=1}^m \alpha_iy^{(i)}\langle x^{(i)},x\rangle+b
\end{align*}

注意：
\begin{itemize}
	\item 整个过程，你不需要$ x^{(i)} $，你只需要它的内积；
	\item 只有少数的样本的内积，即那些支持向量的有关内积是你需要计算的；
\end{itemize}

\section{第八集：核、软间隔、SMO算法}
\subsection{核}
前面的计算表明，我们只需要最大化来得到$ \alpha $，
\begin{align*}
\max\; &W(\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_j\langle x^{(i)},x^{(j)}\rangle\\
s.t.\;& \alpha_i\ge 0\\
& \sum_{i=1}^m y^{(i)}\alpha_i=0
\end{align*}

然后根据\eqref{6-2}式，又有$ w=\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)} $，因此可以计算，
\begin{equation}\label{8-1}
 h_{w,b}(x)=g(w^Tx+b)= \sum_{i=1}^m \alpha_iy^{(i)}\langle x^{(i)},x\rangle+b
\end{equation}


很多时候，我们需要将特征做出如下多项式映射，
\begin{equation}\label{8-3}
 x\rightarrow \begin{bmatrix}
x\\x^2\\x^3\\x^4
\end{bmatrix}\rightarrow \phi(x) 
\end{equation}


那么此时，针对\eqref{8-1}式只需要将$ \langle x^{(i)},x^{(j)}\rangle $替换为$ \langle \phi(x^{(i)}),\phi(x^{(j)})\rangle $即可。但现实总是很残忍，有个$ \phi(x) $是无限维的，此时对于计算机而言，需要把这些向量先储存在内存中然而再求内积，有时这是不可行的。解决该问题，可以引入核函数的概念，
\begin{equation}\label{8-2}
 K(x^{(i)},x^{(j)})=\langle\phi(x^{(i)}),\phi(x^{(j)})\rangle
\end{equation}


\textbf{第一个核函数}，我们来看一个如下的核函数，
\begin{align*}
K(x,z)&= (x^Tz)^2=\left(\sum_{i=1}^nx_iz_i\right)\left(\sum_{j=1}^nx_jz_j\right)\\
& = \sum_{i=1}^n\sum_{j=1}^n(x_ix_j)(z_iz_j)\\
& = (\phi(x))^T(\phi(z))
\end{align*}

其中，\[ \phi(x)=\begin{bmatrix}
x_1x_1\\x_1x_2\\\vdots\\x_1x_n\\x_2x_1\\x_2x_2\\\vdots\\x_2x_n\\\vdots\\x_nx_1\\x_nx_2\\\vdots\\x_nx_n
\end{bmatrix}\hspace{2em} \text{此处的}\phi \text{类似于\eqref{8-3}式的}\phi\text{只取到}x^2\]

也就是说，对于一个需要对所有特征交叉相乘的内积而言（正如上式所表明的），核函数告诉我们，只需要先计算$ x\text{和}z $的内积，然后再平方即可。

\textbf{第二个核函数:多项式核},
\[ K(x,z)=(x^Tz+c)^d \]

它也是可以表示成某个函数的内积。对核函数的一个直观理解：可以认为若要使特征$ x $与$ z $很相似，则他们的核的值应该很大，如果要使特征$ x $与$ z $不相似，则核计算的值应该很小。例如下面这个\textbf{高斯核}就能很好的表达这种思路，
\[ K(x,z)=\exp\left(-\frac{\parallel x-z\parallel^2}{2\sigma^2}  \right) \]

\textbf{所谓核无非就是可以找到一个映射$ \phi $，然后核可以把这个映射表示成一个内积。}那么满足什么样的条件才能保证可以找到这样的映射呢？简单地说，只要矩阵$ K\in R^{m\times m} $是正定的就可以，其中，
\[ K_{ij}=K(x^{(i)},x^{(j)}) \]

支持向量机中，当你在做替换$ \langle x^{(i)},x^{(j)}\rangle \longrightarrow K(x^{(i)},x^{(j)})$的时候，实际上你在隐式地做了一个映射$ x^{(i)}\longrightarrow \phi(x^{(i)}) $，这个映射可能是无限维的，譬如高斯核就是一个无限维的映射\textbf{。对一个一维的特征而言，可能原始特征是线性不可分的，但当你把它映射到无限维空间以后，很可能就线性可分了，这就是SVM。}

任何算法，包括logitic，局部线性回归等，你若可以将特征写成内积，那么就可以利用核函数的概念。实际上，它们是可以写成内积的。

\subsection{软间隔}
如果线性不可分怎么办？或者有一些异常值出现了怎么办，我们宁可不考虑它。此时最优规划可以写成，
\begin{align*}
\min_{w,b,\xi_i}\;& \frac{1}{2}\parallel w\parallel^2+C\sum_{i=1}^m \xi_i\\
s.t.\;& y^{(i)} (w^Tx+b)\ge 1-\xi_i\\
& \xi_i\ge 0
\end{align*}

约束中加入$ \xi_i $是错误分类，目标函数加入$ \xi_i $是表明我们不鼓励这种行为。按照和前面一样的推导思路，
\[ \ell = \frac{1}{2}\parallel w\parallel^2+C\sum_{i=1}^m \xi_i-\sum_{i=1}^m\alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1+\xi_i]-\sum_{i=1}^mr_i\xi_i\]

然后根据拉格朗日对偶，最后可以得到，
\begin{align}\nonumber
\max_{\alpha}\;& W(\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2} \sum_{i=1}^m\sum_{j=1}^my^{(i)}y^{(j)}\alpha_i\alpha_j\langle x^{(i)},x^{(j)}\rangle\\\label{eq8-3}
s.t.& \sum_{i=1}^m y^{(i)}\alpha_i=0\\
& 0\le \alpha_i\le C
\end{align}

它与\eqref{7-1}式唯一的区别在于$ 0\le \alpha_i\le C $。


\subsection{SMO算法}
\textbf{坐标上升法}

对于优化问题，
\[ \max W(\alpha_1,\cdots,\alpha_m)\hspace{2em}\text{无其他关于}\alpha\text{的约束} \]
\begin{verbatim}
for i in 1:m {
\end{verbatim}
\begin{flalign}
 \alpha_i:=\arg\max_{\hat \alpha_i} W(\alpha_1,\cdots,\hat\alpha_i,\alpha_{i+1},\cdots,\alpha_m)
\end{flalign} 
\begin{verbatim}
}
\end{verbatim}

实际上，当$ m $很大的时候，没有必要按照从1到$ m $的顺序，可以选择一些跨度最大的点进行。相对于牛顿法，坐标上升法迭代次数更多,但代价更小。


\textbf{SMO：序列最小优化算法}

坐标上升法不能直接应用SVM，因为我们还有其他约束条件。SMO算法认为一次可以改变两个$ \alpha_i $进行算法。其框架如下，
\begin{itemize}
	\item 选两个$ \alpha_i,\alpha_j $，启发式的选；
	\item 除了$ \alpha_i,\alpha_j $之外，保持其他$ \alpha $不变，在约束条件下关于$ \alpha_i,\alpha_j $优化$ W(\alpha) $
\end{itemize}

具体地，现在保持其他$ \alpha $不变，来更新$\alpha_1,\alpha_2  $，我们知道$ \sum_{i=1}^m\alpha_iy^{(i)}=0 $，因此有，
\[ \alpha_1y^{(1)}+\alpha_2y^{(2)}=-\sum_{i=3}^m\alpha_iy^{(i)}=\zeta\hspace{2em} \text{此时}\zeta\text{是已知的}\]

那么一方面$ 0\le \alpha_i\le C,i\in \{1,2\} $表明这个约束是一个长方形，另一方面$ \alpha_1y^{(1)}+\alpha_2y^{(2)}=\zeta \Longrightarrow \alpha_1=\frac{\zeta-\alpha_2y^{(2)}}{y^{(1)}}$是该$ (\alpha_1,\alpha_2) $平面的一根直线，它们共同构成了关于$ \alpha_i,i\in\{1,2\} $的约束域。此时最优问题可以写为，
\begin{align*}
W(\alpha_1,\alpha_2,\alpha_3,\cdots)&=W\left(\frac{\zeta-\alpha_2y^{(2)}}{y^{(1)}},\alpha_2,\alpha_3,\cdots\right) \\
& = a\alpha_2^2+b\alpha_2+c\hspace{2em}\text{根据\eqref{8-3}式，}W(\alpha)\text{是关于}\alpha\text{的一个二次函数}
\end{align*} 

上式是一个二次函数很容易得到最优值，此时只需要在根据约束来确定$ \alpha_2 $，即一方面你知道解必然在直线$ \alpha_1y^{(1)}+\alpha_2y^{(2)}=\zeta $上，另一方面必在方形约束内，实际上解就在位于方形约束的直线的线段上。

\section{第九集：理论性很强}
\subsection{偏差和方差的权衡}
偏差，通俗地说，如果对于一个二次模型，你用线性模型去拟合，这是一个欠拟合的，意味着你即便有大量数据，也不会向真值收敛。

\subsection{Holffding 定理}
令$ z_1,\cdots,z_k $是i.i.d.，伯努利随机变量$ \phi=p(z_i=1) $，再令$ \hat{\phi}=\frac{1}{m}\sum_{i=1}^m z_i $，那么，对于任意给定的正数$ \gamma $，有，
\[ p(|\hat \phi-\phi|>\gamma)\le 2\exp(-2\gamma^2m) \]

\section{第十集：VC维、模型选择（and 特征选择）、}


\section{第十一集：贝叶斯估计，在线学习}
\subsection{贝叶斯估计}
频率学派最大化似然性，他们认为参数有一个真值，我们要把它估计出来，
\[ \max_\theta\; \Pi_i^m p(y^{(i)}|x^{(i)};\theta)  \]

贝叶斯学派则认为参数是一个随机变量，它有一个先验形式，
\[\theta\sim\mathcal{N}(\mu,\sigma^2) \]

然后，给定训练集合$ \mathcal{S}=\{x^{(i)},y^{(i)}\}_{i=1}^m $，就可以计算参数的后验概率，
\[ p(\theta|\mathcal{S})\propto[\Pi_{i=1}^mp(y^{(i)}|x^{(i)},\theta)]p(\theta) \]

对于任何一个新的观测$ x $，有，
\begin{align*}
 p(y|x,\mathcal{S})&=\int_{\theta} p(y|x,\theta)p(\theta|\mathcal{S})d\theta\\
 E(y|x,\mathcal{S})&=\int_{y}yp(y|x,\mathcal{S})dy
\end{align*}

但上述问题都是高维积分，很难获得这些积分值。一般会选择最大化$ p(\theta|\mathcal{S}) $，即，
\[ \theta_{MAP}=\arg\max_{\theta}p(\theta|\mathcal{S})=\arg\max(\Pi_{i=1}^mp(y^{(i)}|x^{(i)},\theta))p(\theta) \]

它与最大似然估计不同在于后面多了一个先验分布$ p(\theta) $。

\subsection{在线学习}
来一个观测值，然后预测一个，然后告诉你真值，循环往复，这就是在线学习的模式。总在线误差定义为，
\[ \sum_{i=1}^m\bm{I}\{\hat{y}^{(i)}\ne y^{(i)} \]

随机梯度下降是一种不错的算法。

\subsection{怎么选模型}
同一个Logistic模型，两个人来做，可能一个人很棒，另一个人认为它没用。

如果你做了一个邮件分类的算法，错误率却高达20\%，怎么办？你至少有以下八个办法，
\begin{itemize}
	\item 增加更多的训练样本；（修正高方差）
	\item 尝试更小的特征集；（修正高方差）
	\item 尝试更大的特征集；（修正高偏误）
	\item 增加邮件标题特征；（修正高偏误）
	\item 更多次地运行梯度下降迭代；（优化算法）
	\item 尝试牛顿算法；（优化算法）
	\item 使用不同的调节参数，如$ \lambda $；（优化目标函数）
		\item 尝试SVM；（优化目标函数）
\end{itemize}

这么多办法，每个都试一遍，也许需要花费很多时间，如果能先验知道哪些办法可以提前排除就太好了。

\textbf{是高方差还是高偏误？}看看你的训练误差和预测误差就可以了，如果两者相差太大，意味着高方差。

\textbf{是算法不收敛？还是目标函数有问题？（即SVM还是贝叶斯Logistic）}？

譬如，你关心加权准确率，
\[ a(\theta)=\sum_{i=1}w^{(i)}\bm{I}\{h_\theta(x^{(i)})=y^{(i)}\} \]

这个权重指的是对“真就是真，假就是假”两种情况的加权。实际上，你关心的就是这个。现在如果已经发现$ a(\theta_{SVM})>a(\theta_{BLR}) $，但由于某种约束，譬如贝叶斯Logistical算法更好算更快，你仍然想使用贝叶斯Logistc模型，你想知道到底是BLR算法不收敛还是目标函数有问题，你可以如下诊断，

如果是，
\begin{align*}
a(\theta_{SVM})>a(\theta_{BLR})\\J(\theta_{SVM})>J(\theta_{BLR})
\end{align*}

此时问题处在算法上。

如果是，
\begin{align*}
a(\theta_{SVM})>a(\theta_{BLR})\\J(\theta_{SVM})<J(\theta_{BLR})
\end{align*}

此时问题可能处在目标函数上了。

\subsection{误差分析和销蚀分析}
误差分析，将模型与最完美的情况进行比较，观察精度的提升。

销蚀分析，将你使用良好的模型逐一去除某一个组件，观察精度的下降。

\section{第12集：K均值聚类、混合高斯模型、EM算法}
\subsection{K均值聚类}
算法看书；

算法收敛：是局部最优的，可以随机多次选几个初始点，然后找一个最优的；

如何选择类的个数？类的数量往往是模糊的，取决于你怎么想吧，这也是一个可以调整的参数。

\subsection{混合高斯模型}
存在一个隐含的随机变量$ z $，对于$ x^{(i)},z^{(I)} $有联合分布，
\[ p(x^{(i)},z^{(i)})=p(x^{(i)}|z^{(i)})p(z^{(i)}) \]

其中$ z $服从多项式分布$ z\sim Multinominal(\phi)(\phi_j\ge 0,\sum_{j=1}\phi_j=1) $，若是2分类就是伯努利分布了。然后有，
\[ x^{(i)}|z^{(i)}=j\sim\mathcal{N}(\mu_j,\Sigma_j) \]

如果你知道$ z $的类别，则可以使用似然估计得到所有参数，似然函数为，
\[ \ell(\phi,\mu,\Sigma)=\sum_{i=1}^m\ln p(x^{(i)},z^{(i)};\phi,\mu,\Sigma) \]

估计可以得到，
\begin{align*}
\phi_j&=\frac{1}{m}\sum_{i=1}^m\bm{I}\{z^{(i)}=j\}\\
\mu_j&=\frac{\sum_{i=1}^m\bm{I}\{z^{(i)}=j\}x^{(i)}}{\sum_{j=1}^m\bm{I}\{z^{(i)}=j\}}
\end{align*}

\textbf{如果此时你知道了$ z $的类别，当然可以算出诸参数，但问题是你不知道。但你可以猜测一个$ z $，然后不断迭代，这就是EM算法的思路。}具体地，

EM算法中的E步（猜一个$ z^{(i)} $）,令，
\begin{align*}
w^{(i)}_j&:= p(z^{(i)}=j|x^{(i)};\phi,\mu;\Sigma)\\
& = \frac{p(x^{(i)}|z^{(i)}=j)p(z^{(i)}=j)}{\sum_{l=1}^{L}p(x^{(i)}|z^{(i)}=l)p(z^{(i)}=l)}\\
& = \frac{\frac{1}{(2\pi)^{\phi_j/2}|\Sigma_j|^{0.5}}\exp[(x^{(i)}-\mu_j)^T\Sigma_j^{-1}(x^{(i)}-\mu_j)]\phi_j}{\sum_{l=1}^L\frac{1}{(2\pi)^{\phi_l/2}|\Sigma_l|^{0.5}}\exp[(x^{(i)}-\mu_l)^T\Sigma_l^{-1}(x^{(i)}-\mu_l)]\phi_l}
\end{align*}

EM算法中的M步（极大似然估计以更新参数），
\begin{align*}
\phi_j&:=\frac{1}{m}\sum_{i=1}^mw_j^{(i)}\\
\mu_j&:=\frac{\sum_{i=1}^mw_j^{(i)}x^{(i)}}{\sum_{i=1}^mw_j^{(i)}}\\
\Sigma_j&:=\frac{\sum_{i=1}^mw_j^{(i)}(x^{(i)}-\mu_j)(x^{(i)}-\mu_j)^T}{\sum_{i=1}^mw_j^{(i)}}
\end{align*}

\subsection{EM 算法的一般形式}
从Jesen不等式来导出EM算法的一般形式。
\begin{thm}[Jesen 不等式]
$ f $是一个凸函数（例如，$ f"(x)\ge 0 $），$ x $是一个随机变量，然后有，
\[ f(Ex)\le E[f(x)] \]
\end{thm}

特别地，若$ f"(X)>0 $，则
\[ E[f(x)]=f(Ex)\Longleftrightarrow x=E[x]\;\;w.p. 1 \]

同时，若$ f $是一个凹函数（例如，$ f"(x)\le 0 $），$ x $是一个随机变量，然后有，
\[ f(Ex)\ge E[f(x)] \]

那么EM算法的问题是这样，有一个模型$ p(x,z|\theta) $，但仅$ x $可观测，我们想最大化似然函数，
\begin{align*}
 \ell(\theta)&=\sum_{i=1}^m\ln p(x^{(i)};\theta) \\
 & =
\end{align*}

\begin{align*}
&\max_\theta\sum_{i=1}^m\ln p(x^{(i)};\theta)\\
=  & \sum_{i=1}^m \ln\sum_{z^{(i)}}p(x^{(i)},z^{(i)};\theta)\\
=& \sum_{i=1}^m\ln\sum_{z^{(i)}}Q_i(z^{(i)})\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\hspace{2em}(Q_i(z^{(i)})\ge 0,\sum_{z^{(i)}}Q_i(z^{(i)})=1)\\
= & \sum_{i=1}\ln E_{z^{(i)}\sim Q_i}\left[\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\right]\hspace{2em}(\text{因为}Q_i\text{可以看作是$ z_i $的概率，中括号里面的又是关于$z_i$的函数})\\
\ge & \sum_{i=1}^m E_{z^{(i)}\sim Q_i}\left[\ln \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\right]\hspace{2em}(\text{根据Jesen不等式})\\
= & \sum_{i=1}^m\sum_{z^{(i)}} Q_i(z^{(i)})\ln\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}
\end{align*}

我们想要$ \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} $是一个常数（这样Jesen不等式的等号就可以成立，常数的期望等于常数），也就是需要$ Q_i(z^{(i)})\propto p(x^{(i)},z^{(i)};\theta) $，也就是说无论$ z^{(i)} $取何值，不影响$  \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} $，那么实际上$Q_i(z^{(i)}$最好就是，
\begin{align*}
Q_i(z^{(i)})&=\frac{p(x^{(i)},z^{(i)};\theta)}{\sum_{z^{(i)}}p(x^{(i)},z^{(i)};\theta)}\\
& = \frac{p(x^{(i)},z^{(i)};\theta)}{p(x^{(i)};\theta)}\\
& = p(z^{(i)}|x^{(i)};\theta)
\end{align*}

\textbf{一般的EM算法就是}，\begin{itemize}
	\item E步：设置,
	\[ Q_i(z^{(i)})=p(z^{(i)}|x^{(i)};\theta) \text{\hspace{2em}（保持Jesen不等式是紧的）}\]
	\item M步：\[ \theta:=\arg\max_\theta\sum_{i=1}^m\sum_{z^{(i)}} Q_i(z^{(i)})\ln\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\]
\end{itemize}

\section{第13集：EM算法的另一种理解、因子分析}
\subsection{坐标上升法的EM算法理解}
理解EM算法的另一种形式。

定义，
\[ J(\theta,Q)=\sum_{i=1}^m\sum_{z^{(i)}}Q_i(z^{(i)})\ln \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\]

由Jesen不等式，有，
\[ \ell(\theta)\ge J(\theta,Q) \]

EM算法实际上也是一种关于$ J(\theta,Q) $的坐标上升法，
\begin{itemize}
	\item E步是关于$ Q $最大化；
	\item M步是关于$ \theta $最大化；
\end{itemize}

\subsection{高斯混合模型的EM算法推导}
高斯混合模型：
\begin{itemize}
	\item E步：
	\begin{align*}
	Q(z^{(i)}=j)=& p(z^{(i)}=j|x^{(i)},\phi ,\mu,\Sigma)\\
	=&\frac{p(x^{(i)}|z^{(i)}=j)p(z^{(i)}=j)}{\sum_{l=1}^{L}p(x^{(i)}|z^{(i)}=l)p(z^{(i)}=l)}\text{\hspace{2em}（分子第一项是高斯分布，第二项是多项式分布）}
	\end{align*}
	\item M步：
	\[ \max_{\mu,\phi,\Sigma}\sum_{i=1}^m\sum_{z^{(i)}} Q_i(z^{(i)})\ln\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \]
\end{itemize}

\subsection{混合朴素贝叶斯模型：一个文本聚类的例子}
一个文本集合$ \{x^{(1)},\cdots,x^{(m)}\},x^{(i)}\in\{0,1\}^n,x^{(i)}_j=\bm{I}\{\text{文本$j$是否出现在文件$ i $中}\} $，存在一个隐变量，$ z^{(i)}\in\{0,1\},z^{(i)}\sim Bernulli(\phi) $，于是有，
\begin{align*}
p(x^{(i)}|z^{(i)})&=\Pi_{j=1}^np(x^{(i)}_j|z^{(i)})\\
p(x^{(i)}_j=1|z^{(i)}=0)&=\phi_{j|z=0}
\end{align*}

\subsection{因子分析}
问题的引出：

$ m\gg n $时，混合高斯模型还是可以搞定的。但是$ m\approx n $或$ m\ll n $时，混合高斯模型对协方差矩阵的求解中会碰到该矩阵是奇异从而无法求逆的问题。

因子分析可以解决这个问题,存在隐变量$ z $，
\begin{align*}
 z&\sim \mathcal{N}(0,I),\hspace{2em}z\in R^d(d<n) \\
 x|z &\sim \mathcal{N}(\mu+\Lambda z,\Psi)
\end{align*}

也即，
\[ x=\mu+\Lambda z+\varepsilon,\hspace{2em}\epsilon\sim\mathcal{N}(0,\Psi) \]

其中$ \mu\in R^n,\Lambda\in R^{n\times d},\Psi\in R^{n\times n} (\text{对角阵})$。

现在来举一个简单的例子，对于$ z\in R^1,x\in R^2,z^{(i)}\sim\mathcal{N}(0,1) $，然后再有
\[ \Lambda=  \begin{bmatrix}
2\\1
\end{bmatrix},\mu=\begin{bmatrix}
0\\0
\end{bmatrix},\Psi=\begin{bmatrix}
1&0\\0&2
\end{bmatrix} \]

\textbf{画一个图，首先从一维空间中取样$ z $，然后通过$ \mu+\Lambda z $把它变到了一个二维空间的一条直线，然后取一些噪声，使得更像一个二维空间的数据。而实际上，不过是一维空间的点加上一些噪声得到了二维的点。这是对因子分析的一个非正式理解。}

如何拟合因子模型？

先看一些典型事实，
\[ x=\begin{bmatrix}
x_1\\x_2
\end{bmatrix},\hspace{2em}x_1\in R^r,x_2\in R^s,x\in R^{r+s} \]
\[ x\sim\mathcal{N}(\mu,\Sigma),\mu= \begin{bmatrix}
\mu_1\\\mu_2
\end{bmatrix},\Sigma=\begin{bmatrix}
\Sigma_{11}&\Sigma_{12}\\\Sigma_{21}&\Sigma_{22}
\end{bmatrix}\]

\section{第14集：因子分析EM算法的推导、主成分分析}
\subsection{因子分析}
\subsection{主成分分析}
\begin{thm}
	如果向量$ \parallel u\parallel=1 $，那么向量$ x^{(i)} $在$ u $上的投影的长度为$ x^{(i)T}u $。
\end{thm}

那么主成分分析就是选择一个这样的$ u $，使得，
\begin{align*}
& \max_{u:\parallel u\parallel=1}\; \frac{1}{m}\sum_{i=1}^m(x^{(i)T}u)^2 \\
=& \max_{u:\parallel u\parallel=1}\;\frac{1}{m}\sum_{i=1}^m(u^Tx^{(i)})(x^{(i)T}u)\\
= &\max_{u:\parallel u\parallel=1}\;u^T\left[\frac{1}{m}\sum_{i=1}^mx^{(i)}x^{(i)T}\right]u
\end{align*}

最后的一个等号表明，$ u $是$ \Sigma=\frac{1}{m}\sum_{i=1}^mx^{(i)}x^{(i)T} $的主特征向量。\textbf{为什么呢？}回归线性代数，若$ Au=\lambda u $，则称$ u $是矩阵$ A $的特征向量，$ \lambda $是特征值，如果要解一个如下的最优规划，
\begin{align*}
\max&\;u^T\Sigma u\\
s.t. &\; u^Tu=1
\end{align*}

有拉格朗日函数如下，
\[ \mathcal{L}(\mu,\alpha)=u^T\Sigma u-\alpha(u^Tu-1) \]

一阶条件表明，
\[ \nabla_u\mathcal{L}=\Sigma u-\alpha u=0 \]

\subsection{主成分应用}
高维数据可视化：高维数据无法可视化，降到2到3维可以可视化。

压缩数据：不损失数据的信息。

学习理论中的降维：特征很多的话，容易过拟合。此时降维可以。

\textbf{匹配/最佳距离的计算}：譬如人脸识别，若你有一张$ 100\times 100 $像素的照片，那你可以构造一个10000维的特征向量$ x $，然后每张照片就是一个$ x^{(i)} $，如何找到照片中是同一个人的照片呢？若是直接计算10000维的欧式距离是有问题的，因为照片中存在大量的噪音，这些也构成了距离的一部分，这不是我们所希望的。如果我们可以将这10000维的数据降到譬如50维，这些维度是专门管人脸的。此时，可以重新计算这50维的欧式距离就更为恰当。

\section{第15集：奇异值分解、独立成分分析}
\subsection{问题的引出}
前面我们讲了一个例子，特征向量是10000维的，此时它的方差协方差矩阵将是$ 10000\times 10000 $，这是非常巨大的，我们一般不能直接这么干。

\textbf{还有如何衡量两个文本之间的相似性？}

一般可以构造一个如50000个单词的字典，然后比较文本和字典，若在文本中出现字典中的单词，则在相应位置取1，否则取0。这样两个文本就有两个50000维的向量，你可以计算这两个向量的夹角，越小越相似。

但是你是否考虑过这样一种情况。一篇文章是关于study的，一篇是关于learn的，因为这两个单词完全不同，它们的内积将是0，也就意味着完全无关。但显然这不是我们想要的结果。如果我们可以把这两个文本往一个主成分的方向上投影，也许它们就会存在一定的正相关性。

\subsection{奇异值分解}
现在来看看如何具体地解决这些问题。

对于任意一个$ A\in R^{m\times n} $，总有，
\[ A_{m\times n}=U_{m\times n}D_{n\times n}V_{n\times n}^T \hspace{2em}(SVD)\]

其中，
\begin{itemize}
	\item $ D $是一个对角线元素为$ \sigma_1,\cdots,\sigma_n $的对角阵（除对角线外其他元素为0）；
	\item $ U $的列是$ AA^T $的特征向量;
	\item$ V $	的列是$ A^TA $的特征向量；
\end{itemize}

利用上述结论，现在为了得到方差协方差矩阵$ \Sigma=X^TX $的特征值和特征向量，可以对$ X $进行奇异值分解，前面那个文本分析的例子，$ X\in R^{m\times 50000} $。用这种方式的好处在于方差协方差矩阵是$ 50000\times 50000 $，而此时奇异值分解的$ X $是$ m\times 50000 $。

\subsection{独立成分分析(indepengdent component analysis,ICA)}
一房间里面有两个麦克风，每个麦克风搜集了两个声源，从这两个麦克风的录音中区分出两个声源？

具体地，现在假设原始声源有$ n $个，$ s\in R^n $，$ s^{(i)}_j $是第$ j $个演讲者在时间$ i $的信号。

然后我们观察到，
\[ x^{(i)}=As^{(i)}\hspace{2em}x^{(i)}\in R^n(n\text{个麦克风}) \]

令$ x^{(i)}_j $是麦克风$ j $在时间$ i $记录的信号，且$ x^{(i)}_j=\sum_{k}A_{jk}s^{(i)}_k $，因此，我们的目的在于寻找一个矩阵$ W=A^{-1} $，使得$ s^{(i)}=Wx^{(i)} $。

给定样本$ x^{(1)},\cdots,x^{(m)} $，联合似然是，
\[ \mathcal{L}(w)=\sum_{i=1}^m\ln[\Pi_jp_s(w_j^Tx^{(i)})]|w| \]

其中$ p_s(S) $可以选择一个CDF然后求导成为一个密度函数，记住，不能选择高斯密度函数。使用随机梯度下降算法，
\[ w:=w+\alpha\nabla_w\mathcal{L}(w) \]

\section{第16集：强化学习}
强化学习不是一个一次决策过程，它是一个渐次学习的过程。
\subsection{MDP（马氏决策过程）的表述}
\textbf{基本表述：}MDP是一个五元组，$ MDP=\{S,A,p_{sa},\gamma,R\} $，

\begin{itemize}
	\item $ S $：状态集合；
	\item $ A $：行为集合；
	\item $ p_{sa} $：状态转移分布，因此有，$ \sum_{s'}p_{sa}(s')=1,p_{sa}(s')\ge 0 $；
	\item $ \gamma $：贴现因子，$ 0\le \gamma <1 $；
	\item $ R $，奖励函数，$ R:S\rightarrow \bm{R} $；
\end{itemize}

\subsection{MDP的一个例子}
\textbf{一个例子：}譬如对于一个三行四列的矩形阵，机器人要到达右上角那个格子即$ (4,3) $，第二行第二列是一个障碍（无法通过），那么此时，
\begin{itemize}
	\item $ S $：初始状态可以处于非右上角的任意一个方格中，即有11个状态；
	\item $ A=\{N,S,E,W\} $，行动可以东南西北任一方向走；
	\item $ p_{sa} $：一般来讲，指挥机器人譬如往北，由于器械等其他原因，它可能会偏移方向。譬如现在机器人在$ (3,1) $的位置，让它往北，那么，它到达$ (3,2) $的概率只有0.8。具体有，
	\begin{align*}
&	 p_{(3,1),N}[(3,2)]=0.8,\hspace{2em} p_{(3,1),N}[(4,1)]=0.1\\
&	 p_{(3,1),N}[(2,1)]=0.1,\hspace{2em} p_{(3,1),N}[(3,3)]=0
	\end{align*}	
	\item $ R $：可以设定
	\begin{align*}
	&R[(4,3)]=1\\
	&R[(4,2)]=-1\\
	&R(s)=-0.02\hspace{2em}	\text{for other states}
	\end{align*}
\end{itemize}

因此，\textbf{一个MDP的过程如下，}
\begin{align*}
\text{在状态}s_0,\text{选择行动}a_0,&\text{得到下一个状态}s_1\sim p_{s_0a_0}\\
\text{在状态}s_1,\text{选择行动}a_1,&\text{得到下一个状态}s_2\sim p_{s_1a_1}\\
&\vdots
\end{align*}

这样，对于机器人所经历的每一个状态，我们有一个奖励函数，并要用贴现因子将其加总作为总回报，
\[ R(s_0)+\gamma R(s_1)+\gamma^2R(s_2)+\cdots \]

总的目的就是选择一系列行动$ (a_0,a_1\cdots) $以最大化期望总回报，
\[ E[R(s_0)+\gamma R(s_1)+\gamma^2R(s_2)+\cdots] \]

这就有一个政策函数，$ \pi:S\rightarrow A $。对于本例而言，政策函数如下的左边所示，右边为值函数，
\begin{table}[H]
	\centering
	\caption{最优政策函数和值函数}\label{t1}
\begin{tabular}{|c|c|c|c|}\hline
$\rightarrow$ & $\rightarrow$ & $\rightarrow$ &$+1$\\\hline
$ \uparrow $&shadow & $\uparrow$ & $ -1 $\\\hline
$ \uparrow $&$ \leftarrow $&$ \leftarrow $&$ \leftarrow $\\\hline
\end{tabular}
\hspace{2em}
\begin{tabular}{|c|c|c|c|}\hline
	0.86 & 0.9 & 0.93 &$+1$\\\hline
0.82&shadow & 0.69 & $ -1 $\\\hline
0.78&0.75&0.71&0.45\\\hline
\end{tabular}\end{table}

\textbf{下面对$ V^\pi,V^*,\pi^* $做一些定义：}

	对任意的政策$ \pi $，\textbf{定义值函数$ V^\pi:S\rightarrow \bm{R} $}，$ V^\pi(s) $是从状态$ s $开始，执行$ \pi $的期望总收益，也即，
	\[V^\pi(s)=E[R(s_0)+\gamma R(s_1)+\gamma^2R(s_2)+\cdots|\pi,s_0=s]  \]

看一个如下的政策，左边是政策$ \pi $，右边是对应的$ V^\pi $，
\begin{table}[H]
	\centering	
	\begin{tabular}{|c|c|c|c|}\hline
		$\leftarrow$ & $\leftarrow$ & $\leftarrow$ &$+1$\\\hline
		$ \downarrow $&shadow & $\leftarrow$ & $ -1 $\\\hline
		$ \rightarrow $&$ \rightarrow $&$ \uparrow $&$ \uparrow $\\\hline
	\end{tabular}\hspace{2em}
	\begin{tabular}{|c|c|c|c|}\hline
	0.52 & 0.73& 0.77 &$+1$\\\hline
	$ -0.9 $&shadow & -0.82 & $ -1$ \\\hline
	-0.88&-0.87&-0.85&$-1$\\\hline
\end{tabular}
\end{table}

再来看关注$ V^\pi $，看到，
\[V^\pi(s)=E[R(s_0)+\gamma \underbrace{(R(s_1)+\gamma R(s_2)+\cdots)}_{V^\pi(s_1)}|\pi,s_0=s]  \]

但考虑到在状态$ s $转移到下一个状态$ s' $存在一个概率，那么下一个状态的$ V^{\pi}(s') $ 实际上是一个期望，因此，上式应该写成，

\[V^\pi(s)=R(s)+\gamma \sum_{s'}p_{s\pi(s)}(s')V^\pi(s')  \]

上式也称为贝尔曼方程。可以用一个数值例子更加显示地阐述，若现在处于$ (3,1) $这个位置，此时最佳行动为北方，那么，
\[ V^\pi[(3,1)]=R[(3,1)]+\gamma [0.8\cdot V^\pi((3,2))+0.1\cdot V^\pi((4,1))+0.1\cdot V^\pi((2,1))] \]

实际上，你会有11个状态，上面只是其中一个。然后你会有11个类似上式的方程，然后有11个未知数，你当然可以解一个这样的线性方程组。

\textbf{最优值函数$ V^*(s) $和最优政策函数$ \pi^*(s) $}，
\[ V^*(s)=\max_{\pi}V^\pi(s) \]

利用贝尔曼方程，就可以写为，
\[V^*(s)=R(s)+\max_a\gamma \sum_{s'}p_{sa}(s')V^*(s')  \]

同时，有，
\[ \pi^*(s)=\arg\max_a\sum_{s'}p_{sa}(s)V^*(s') \]
\subsection{估计方法}
现在来讨论算法，\textbf{值函数迭代}，
\begin{enumerate}
	\item 初始化$ V(s)=0,\forall s $；
	\item 对每一个$ s $，进行如下更新操作，
	\[ V(s):=R(s)+\max_a\gamma\sum_{s'}p_{sa}(s')V(s') \]
\end{enumerate}

现在可以回头看看在$ (3,1) $时，为何往西更好而不是往北，可以利用上述第二步计算往西和往北的最优值函数如下，
\begin{align*}
W:& \max_a\gamma\sum_{s'}p_{sa}(s')V(s')=0.8\cdot 0.75+0.1\cdot 0.69+0.1\cdot 0.7=0.78\\
N:& \max_a\gamma\sum_{s'}p_{sa}(s')V(s')=0.8\cdot 0.69+0.1\cdot 0.75+0.1\cdot 0.49=0.676
\end{align*}

\textbf{政策函数迭代}，
\begin{enumerate}
	\item 随机初始化$ \pi $；
	\item 重复以下动作，令，
	\begin{align*}
	V&:=V^\pi \hspace{2em}\text{类似于前面那个11个未知数11个方程的求解}\\
	 \pi(s)&:=\arg\max_a\sum_{s'}p_{sa}V(s')\hspace{2em}\text{更新政策函数}
	\end{align*}
\end{enumerate}

因此，当你的可选政策行为比较少时，比如上面11个方程的系统，政策迭代往往可以比较好地解决问题。如果政策行为较多，也许值函数迭代更好。

如果我们并不知道转移矩阵怎么办？本例中可以如下估计，
\[ p_{sa}(s')=\frac{\sharp \text{times take action "a" in $s$ got to }s'}{\sharp \text{times took aciton "a" in } s} \]

一般的一个马氏决策过程算法就是如下循环：
\begin{enumerate}
	\item 使用$ \pi $以获取马氏决策过程的经验；
	\item 更新你的概率转移矩阵$ p_{sa} $；
	\item 使用值函数迭代（或政策迭代）解贝尔曼方程以得到值函数$ V $:
	\item 更新策略$ \pi(s)=\arg\max_a \sum_{s'}p_{sa}V(s') $
\end{enumerate}

\section{第17集}
回顾上一节的例子，对于一个MDP五元组，$ MDP(S,A,\{p_{sa}\},\gamma,R) $，
\begin{table}[H]
\begin{tabular}{cc}
	$S$:&11个\\
$A$:&\{N,S,W,E\}\\
$ p_{sa} $:&0.8,0.1,0.1\\
$ R $:&$\pm 1,-0.02$\\
$ \gamma $:&0.99
\end{tabular}
\end{table}

目标是找到一个策略$ \pi:S\rightarrow A $以最大化值函数$ V^\pi(s) $

